package net.xuele.learn.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Demo {

    @Test
    public void run() {
        int n = 2;
        ListNode head = new ListNode(1);
        ListNode l2 = new ListNode(2);
        head.next = l2;
        ListNode l3 = new ListNode(3);
        l2.next = l3;
        ListNode l4 = new ListNode(4);
        l3.next = l4;
        ListNode l5 = new ListNode(5);
        l4.next = l5;

//        ListNode listNode = swapPairs(l1);

//        ListNode listNode = reverseList(l1);
//        while (head.next != null && n - 1 > 0) {
//            head = head.next;
//            n--;
//        }
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            head = head.next;
        }

        System.out.println(head);


    }

    /**
     * 2
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {


        return null;
    }


    /**
     * 两链表相交
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == null || headB == null) {
            return null;
        }
        ListNode result = null;
        ListNode temp = headB;
        while (headA.next != null) {
            result = headA.next;
            if (result == headB.next) {
                break;
            } else {
                result = null;
                headB = headB.next;
            }
            // 最后一个节点了！！！
            if (headB == null) {
                headA = headA.next;
                headB = temp;
            }

        }
        return result;
    }


    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {


        if (head == null || head.next == null) {
            return head;
        }
        ListNode list = reverseList(head.next);

        head.next.next = head;
        head.next = null;

        return list;

    }


    /**
     * 19
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int tmp = n;
        if (n <= 0) {
            return head;
        }
        ListNode h = head;
        ListNode g = head;

        while (g.next != null) {
            g = g.next;
            if (n > 0) {
                n--;
            } else {
                head = head.next;
            }
        }

        //此时g为最后一个节点了，head为倒数第n个


        if (g == h) {
            return null;
        }

        if (head == h) {
            if (tmp == 2) {
                h = head.next;
                head = null;
                return h;
            } else {
                head.next = null;
                return h;
            }

        }

        head.next.next = null;
        head.next = g;

        return h;
    }


    /**
     * 18
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> result = new ArrayList<>();

        if (nums.length < 4) {
            return null;
        }

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int rest = target - num;

        }


        return result;
    }


    /**
     * LeetCode----24
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        ListNode oldHead = head;
        ListNode newHead = null;
        ListNode list = null;
        if (head != null && head.next == null) {
            return head;
        }
        while (head != null && head.next != null) {
            if (head == oldHead) {
                newHead = head.next;
            }
            // node = 2
            ListNode node = head.next;

            ListNode nextNode = node.next;

            // 交换节点
            // 2-1
            node.next = head;
            // 暂且仅交换
            // 断开与2的关系
            head.next = null;
            // 到此交换完成

            if (head == oldHead) {
                list = head;
            } else {
                list.next = node;
                list = head;
            }
            // 并将
            head = nextNode;
            if (head != null && head.next == null) {
                list.next = head;
            }
        }

        return newHead;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }


    /**
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * <p>
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * <p>
     * 注意：给定 n 是一个正整数。
     * <p>
     * 示例 1：
     * <p>
     * 输入： 2
     * 输出： 2
     * 解释： 有两种方法可以爬到楼顶。
     * 1.  1 阶 + 1 阶
     * 2.  2 阶
     * 示例 2：
     * <p>
     * 输入： 3
     * 输出： 3
     * 解释： 有三种方法可以爬到楼顶。
     * 1.  1 阶 + 1 阶 + 1 阶
     * 2.  1 阶 + 2 阶
     * 3.  2 阶 + 1 阶
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/climbing-stairs
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        //　出现1的次数
        int time = n;
        // 可以组合成2的次数
        int twice = n / 2;
        for (int i = 1; i <= twice; i++) {
            // 位数
            int tmp = n - i;

        }
        return 0;
    }
}
